class Solution {
public:
    void dfs(int index)
    {
        if (path.size() == _k)
        {
            ret.push_back(path);
            return;
        }

        for (int i = index; i <= _n; ++i)
        {
            path.push_back(i);
            dfs(i + 1);

            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        _n = n, _k = k;
        dfs(1);
        return ret;
    }
private:
    vector<vector<int>> ret;
    vector<int> path;
    int _n;
    int _k;
};